package com.hdu.hot100.stack;

public class lc84 {
    class Solution {
        public int largestRectangleArea(int[] heights) {
            int len = heights.length;
            int[] stack = new int[len];
            int r = 0;
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < len; i++)
            {
                if (r == 0 || heights[i] > heights[stack[r - 1]])
                {
                    stack[r++] = i;
                }
                else if (heights[i] == heights[stack[r - 1]])
                {
                    r--;
                    stack[r++] = i;
                }
                else
                {
                    while (r > 0 && heights[i] < heights[stack[r - 1]])
                    {
                        int index = stack[--r];
                        int left = r == 0 ? - 1 : stack[r - 1];
                        int height = heights[index];
                        int width = i - left - 1;
                        ans = Math.max(ans, height * width);
                    }
                    stack[r++] = i;
                }
            }
            while (r > 0)
            {
                int index = stack[--r];
                int left = r == 0 ? - 1 : stack[r - 1];
                int height = heights[index];
                int width = len - left - 1;
                ans = Math.max(ans, height * width);
            }
            return ans;
        }
    }
}
